package com.zou.dataStruct.Graph.Array;

//矩阵构造
public class Dijkstra {

    private static int N = 1000;
    private static int[][] Graph = {
            { 0, 1, 5, N, N, N, N, N, N },
            { 1, 0, 3, 7, 5, N, N, N, N },
            { 5, 3, 0, N, 1, 7, N, N, N },
            { N, 7, N, 0, 2, N, 3, N, N },
            { N, 5, 1, 2, 0, 3, 6, 9, N },
            { N, N, 7, N, 3, 0, N, 5, N },
            { N, N, N, 3, 6, N, 0, 2, 7 },
            { N, N, N, N, 9, 5, 2, 0, 4 },
            { N, N, N, N, N, N, 7, 4, 0 } };

    public static void main(String[] args) {
        dijkstra(0, Graph);
    }

    /**
     * Dijkstra最短路径。
     * @param vs 起始节点
     * @param Graph 图
     */
    public static void dijkstra(int vs, int[][] Graph){
        int n = Graph.length;
        int []pre = new int[n];//前驱结点数组
        int []mindisk = new int[n];
        boolean []find = new boolean[n];

        for(int i=0;i<n;i++){
            pre[i] = i;
            mindisk[i] = Graph[vs][i];
        }

        int vnode = 0;
        find[vs] = true;

        for(int k=1;k<n;k++){
            int min = N;
            for(int j=0;j<n;j++){
                if(!find[j]&&mindisk[j]<min){
                    min = mindisk[j];
                    vnode = j;
                }
            }
            find[vnode] = true;
            for(int j=0;j<n;j++){
                if(!find[j]&&min+Graph[vnode][j]<mindisk[j]){
                    mindisk[j] = min+Graph[vnode][j];
                    pre[j] = vnode;
                }
            }
        }
        for(int i=0;i<n;i++){
            System.out.print("V"+vs+"到达"+"V"+i+"的最短距离S是:"+mindisk[i]);
            System.out.println("("+"V"+pre[i]+"->"+"V"+i+")");
        }
    }
}
